Autumn Stage 4 Obsidian Vault
Modules
Digital Communications
Information Theory
Networks and Internet Systems
Software Engineering

Module Overview

[Lecture on 1.3]

Professor John Murphy
j.murphy@ucd.ie

You are expected to attend all lectures - they are not recorded and there will be important information not included in the emails.

Textbook

"Computer Networks, 5th ed"
Prentice Hall 2010
Andrew S. Tanenbaum and Wetherall

Entirely optional - notes should be sufficient.

Problem Sets

Problem sets will be given out
They are not graded or handed up, they're practice

Assessments

Four in-class tests

Provisional dates:
Test 1: Friday October 4th (11 am) 10% (Week 4)
Test 2: Friday October 25th (11 am) 20% (Week 7)
Test 3: Friday November 15th (11 am) 30% (Week 10)
Final Exam (on-campus with laptop) in the exam period - 40%

We'll get letter grades for each one (I think ?) then he uses the calculation points system for final grades.

Switching

Motivation

Two extreme topologies:
Mesh vs. central
Pasted image 20240911102304.pngPasted image 20240911102314.png

Mesh obviously requires way too many links
Central has drawbacks:

  • Single point of failure (router)
  • Single link failure cuts off a node
  • Enormous traffic at router node
  • Potentially wasteful if lots of communications are to 'nearby' devices

So we'll need something inbetween

  • So what is the optimum number of switches?
  • Limit on scale of a single switch.
  • Reliability of a single switch is also limited.

Two kinds of link:

  • User to switch ('access link')
  • Switch to switch

You get topologies that could look like this:
Pasted image 20240911102559.png

Example
  • In Ireland there are 5 million phones
  • Connected by about 10k mobile masts
  • These are connected by ~100 major switches
    So
  • 500 phones per mast
  • 50,000 phones per major switch
  • Switches connected through a backbone network (backbone could be as few as 5-6 massive switches)

Switch Considerations

  • How to measure performance?
  • Cost to build switch
  • Number of inputs/outputs
  • Can all possible connections be switched?
  • How does the switch grow with connection count
  • Functionality and technology of the switch (not on this module)

Strictly Non-Blocking Switch

  • Device that can connect any of n inputs to any of m outputs
    • Provided the output is not busy
    • 1-1 connections only
  • This is called a 'strictly non-blocking switch'
    • i.e. any connection can be made (if they're free), so it should never block a connection

Switch Structure - Ports

Pasted image 20240911103537.png

Non-Strict Non-Blocking Switch

  • Weaker alternatives to strictly non-blocking switch

  • Non-blocking with Rearrangement:

    • Allows any connection to be made, but may require other existing connections be rearranged

  • Non-Blocking with Connection Packing Rule

    • Non-blocking as long as the connections are put up in a particular order

Some blocking may be acceptable if it's small enough.

Crosspoints

  • Switching gets much more difficult with scale - we'll look at generally 1000 ports
  • Input/output is a bit of an abstract idea, in reality they are usually one and the same
  • Crosspoint: connects an input to an output.
    • We often want to minimise how many we need as they may be expensive

Basic analogue crosspoint:
Pasted image 20240911103957.png

Crossbar Switch

Pasted image 20240911104047.png
Each crosspoint here can be enabled to link the two wires passing under it

Consider that this switch has 512 possible configurations, the vast majority of which are not very useful. This may suggest that there are too many crosspoints ( crosspoints)

Modern crosspoints are electronic transistors
See also: Time Switching

[End of lecture on 1.3]
[Lecture on 1.5]

Switch Design

  • Usually we will look at square switches (equal inputs and output)
  • Want to minimise the number of crosspoints C() as each one has an associated cost
  • Multi-stage switches are one option
  • Clos Networks are the key idea

Clos Switch

Clos Networks
  • Three stage switch
  • Pasted image 20240913111142.png
  • Notice the switches on the right have transposed dimensions from the ones on the left
  • sometimes
  • Strictly non-blocking

  • input switches (each is an -> crossbar)

  • center switches (each is -> crossbar)

  • output switches (each is a -> crossbar)

  • You can apply this idea recursively, turning the center stage (of crossbars) into its own Clos network

Number of crosspoints:

  • Input stage:
  • Output stage: Same again
  • Center stage:

Noting that , you get
Total:

Optimal value is and giving

For , this beats a crossbar.

You'll need to round up or down to an integer usually - generally you should attempt both up and down and see which performs better.

  • Calculate and round it up, then calculate and always round that up (so you have enough ports)
  • Then try again but round down

Recursion

The middle stage has the most switches, so we can eliminate some by replacing that with a 3-stage clos switch, yielding a 5-stage switch.

There is an optimal number of stages for a given value of N

Generally you'll only need 3 or 5 stages, it's only worth implementing more for extremely large switches

Table Of Contents
Module Overview
Textbook
Problem Sets
Assessments
Switching
Motivation
Switch Considerations
Strictly Non-Blocking Switch
Switch Structure - Ports
Non-Strict Non-Blocking Switch
Crosspoints
Switch Design
Clos Switch
Recursion